package com.qch.edu.lagou.algorithm.dp;

/**
 * @Author qch
 * @Date 2021/7/23
 * 0-1背包问题 O（i*j）
 * 有n件物品和一个最大承重为W的背包，每件物品的重量是w[i]，
 * 价值是v[i]在保证总重量不超过W的前提下，选择某些物品装入背包，
 * 背包的最大总价值是多少？
 * （注意：每个物品只有一件，也就是每个物品只能选择0件或者1件分析）
 *
 * dp方程：
 * 如果：1）可以选这一件物品j>w[i]
 *          1.不选：dp[i][j]=dp[i-1][j]
 *          2.选了：：dp[i][j]=v[i]+dp[i-1,j-w[i]]
 *          两者取价值最大的数 :Max(dp[i-1][j],v[i]+dp[i-1,j-w[i]])
 *       2）不可以选这件物品j<w[i]
 *           则：dp[i][j]=dp[i-1][j]
 */
public class Bag2 {
    /**
     * 计算最大价值
     * @param values 物品的价值数组
     * @param weight 物品的重量数组
     * @param max 背包最大承重
     * @return
     */
    public static int MaxVaue(int[] values,int[] weight,int max)
    {
        if(values==null||values.length==0)
        {
            return 0;
        }
        if(weight==null||weight.length==0)
        {
            return 0;
        }
        if(weight.length!=values.length||max<0)
        {
            return 0;
        }
        //dp数组
        int[][]dp=new int[values.length+1][max+1];
        for (int i = 1; i <=values.length; i++) {
            for (int j=1;j<=max;j++){
                //选择的物品超过最大承重
                if(j<weight[i-1])
                {
                    //不能选择该物品
                    dp[i][j]=dp[i-1][j];
                }else {
                    //可选，可不选
                    //上轮最大价值
                    int proValue=dp[i-1][j];
                    //需要理解：为啥是[i-1]
                    int curValue=values[i-1]+dp[i-1][j-weight[i-1]];
                    dp[i][j]=Math.max(proValue,curValue);

                   // dp[i][j] = Math.max((dp[i - 1][j]), values[i - 1] + dp[i - 1][j - weight[i - 1]]);
                }
            }

        }
        return dp[values.length][max];
    }

    public static void main(String[] args) {
        int[] values = {6, 3, 5, 4, 600};
        int[] weights = {2, 2, 6, 5, 4};
        int max = 10;
        System.out.println(MaxVaue(values, weights, max));
    }
}
